Feature #8: Optimal Path

Implement the "Optimal Path" feature for our "Uber" project.

Description#

Uber is one of the most popular ride-hailing applications. It provides a choice of a variety of vehicles to the passengers that use it for transport. Uber always uses an optimal path to save its passenger’s time. The terrain is represented as a 2D grid. A passenger waits on one end of the grid and a driver is present on another end. This feature will show us how to find the optimal path for the driver to get to the passenger.

Created with Fabric.js 3.6.6
Car en route to get a passenger

1 of 7

Created with Fabric.js 3.6.6
Car en route to get a passenger

2 of 7

Created with Fabric.js 3.6.6
Car en route to get a passenger

3 of 7

Created with Fabric.js 3.6.6
Car en route to get a passenger

4 of 7

Created with Fabric.js 3.6.6
Car en route to get a passenger

5 of 7

Created with Fabric.js 3.6.6
Car en route to get a passenger

6 of 7

Created with Fabric.js 3.6.6
Car en route to get a passenger

7 of 7

Solution#

A new path metric is evaluated. The terrain is represented as a 2D grid, and the cost of going from one point to an adjacent one is given as an integer.

Here is how the implementation of this feature will take place:

  1. We can think of this problem as a shortest path problem in a 2D rectangular graph, where the values in the input array are edge weights.

  2. Since the driver can only travel right or downward, the optimal way to get to any of the cells in the first row is to travel right. Thus, we can iteratively calculate the costs along the first row as cost[0][i]=cost[0][i]+cost[0][i−1]cost[0][i] = cost[0][i] + cost[0][i-1] for all i=1,2,i = 1, 2, …, n−1n-1. This process will apply to the highlighted cells below.

11
11
13
13
5
5
4
4
3
3
14
14
8
8
6
6
12
12
10
10
7
7
4
4
5
5
1
1
9
9
11
11
Viewer does not support full SVG 1.1
Operation on the first row of the matrix
  1. Similarly, the optimal cost to every cell in the first column can be computed as cost[j][0]=cost[j][0]+cost[j−1][0]cost[j][0] = cost[j][0] + cost[j-1][0] for all jj = 1,2,1, 2, …, m−1m-1. This process will apply to the highlighted cells below.
11
11
13
13
5
5
3
3
14
14
6
6
12
12
7
7
4
4
5
5
1
1
9
9
11
11
4
4
8
8
10
10
Viewer does not support full SVG 1.1
Operation on the cells of the matrix, except on the first row and column
  1. All other cells can be reached either from the cell above or from the cell to the left. We will pick the option that has the least cost. Thus, cost[i][j]=min(cost[i−1][j],cost[i][j−1])+cost[i][j]cost[i][j] = min(cost[i-1][j], cost[i][j-1]) + cost[i][j] for i=1,2,i = 1, 2, …, n−1n-1 and j=1,2,j = 1, 2, …, m−1m-1. This process will apply to the highlighted cells below.
4
4
3
3
14
14
8
8
6
6
12
12
10
10
7
7
4
4
5
5
1
1
9
9
11
11
11
11
13
13
5
5
Viewer does not support full SVG 1.1
Operation on the first column of the matrix
  1. Finally, cost[m][n] will have the cost of the optimal path from the driver to the waiting passenger.

The following slides illustrate this process:

Created with Fabric.js 3.6.6
Find the optimal path

1 of 17

Created with Fabric.js 3.6.6
Find the optimal path

2 of 17

Created with Fabric.js 3.6.6
Find the optimal path

3 of 17

Created with Fabric.js 3.6.6
Find the optimal path

4 of 17

Created with Fabric.js 3.6.6
Find the optimal path

5 of 17

Created with Fabric.js 3.6.6
Find the optimal path

6 of 17

Created with Fabric.js 3.6.6
Find the optimal path

7 of 17

Created with Fabric.js 3.6.6
Find the optimal path

8 of 17

Created with Fabric.js 3.6.6
Find the optimal path

9 of 17

Created with Fabric.js 3.6.6
Find the optimal path

10 of 17

Created with Fabric.js 3.6.6
Find the optimal path

11 of 17

Created with Fabric.js 3.6.6
Find the optimal path

12 of 17

Created with Fabric.js 3.6.6
Find the optimal path

13 of 17

Created with Fabric.js 3.6.6
Find the optimal path

14 of 17

Created with Fabric.js 3.6.6
Find the optimal path

15 of 17

Created with Fabric.js 3.6.6
Find the optimal path

16 of 17

Created with Fabric.js 3.6.6
Find the optimal path

17 of 17

Let’s look at the code for this solution:

Find optimal path

Complexity measures#

Time complexity Space complexity
O(mn)O(mn) O(1)O(1)

Time complexity#

We will traverse the entire matrix only once. Therefore, the time complexity will be O(mn)O(mn), where mm will represent the number of rows and nn will represent the number of columns.

Space complexity#

We will compute the minimum path sum in place. Therefore, the space complexity will be O(1)O(1).

Feature #7: Highest Rank

What Did We Learn?